{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Star Sum of a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #graph #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #图 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxStarSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图中最大星和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>n</code>&nbsp;个点的无向图，节点从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;编号。给你一个长度为 <code>n</code>&nbsp;下标从&nbsp;<strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>vals</code>&nbsp;，其中&nbsp;<code>vals[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个节点的值。</p>\n",
    "\n",
    "<p>同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条双向边。</p>\n",
    "\n",
    "<p><strong>星图</strong>&nbsp;是给定图中的一个子图，它包含一个中心节点和&nbsp;<code>0</code>&nbsp;个或更多个邻居。换言之，星图是给定图中一个边的子集，且这些边都有一个公共节点。</p>\n",
    "\n",
    "<p>下图分别展示了有 <code>3</code>&nbsp;个和 <code>4</code>&nbsp;个邻居的星图，蓝色节点为中心节点。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-descdrawio.png\" style=\"width: 400px; height: 179px;\"></p>\n",
    "\n",
    "<p><strong>星和</strong> 定义为星图中所有节点值的和。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>k</code>&nbsp;，请你返回 <strong>至多</strong>&nbsp;包含 <code>k</code>&nbsp;条边的星图中的 <strong>最大星和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/07/max-star-sum-example1drawio.png\" style=\"width: 300px; height: 291px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2\n",
    "<b>输出：</b>16\n",
    "<b>解释：</b>上图展示了输入示例。\n",
    "最大星和对应的星图在上图中用蓝色标出。中心节点是 3 ，星图中还包含邻居 1 和 4 。\n",
    "无法得到一个和大于 16 且边数不超过 2 的星图。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>vals = [-5], edges = [], k = 0\n",
    "<b>输出：</b>-5\n",
    "<b>解释：</b>只有一个星图，就是节点 0 自己。\n",
    "所以我们返回 -5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == vals.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= vals[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= min(n * (n - 1) / 2</code><code>, 10<sup>5</sup>)</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= n - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-star-sum-of-a-graph](https://leetcode.cn/problems/maximum-star-sum-of-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-star-sum-of-a-graph](https://leetcode.cn/problems/maximum-star-sum-of-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,10,-10,-20]\\n[[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]\\n2', '[-5]\\n[]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        l = [ [] for _ in range(n) ]\n",
    "        for i, j in edges:\n",
    "            if vals[i] > 0:\n",
    "                l[j].append(vals[i])\n",
    "            if vals[j] > 0:\n",
    "                l[i].append(vals[j])\n",
    "        ret = -inf\n",
    "        for i in range(n):\n",
    "            l[i].sort(reverse=True)\n",
    "            ret = max(ret, vals[i] + sum(l[i][:k]))\n",
    "        return ret\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, V: List[int], E: List[List[int]], k: int) -> int:\n",
    "        G = [[] for _ in range(len(V))]\n",
    "        for u, v in E:\n",
    "            if V[v] > 0: G[u].append(V[v])\n",
    "            if V[u] > 0: G[v].append(V[u])\n",
    "        return max(uv + sum(sorted(vs, reverse=True)[:k]) for uv, vs in zip(V, G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, V: List[int], E: List[List[int]], k: int) -> int:\n",
    "        G = [[] for _ in range(len(V))]\n",
    "        for u, v in E:\n",
    "            if V[v] > 0: G[u].append(V[v])\n",
    "            if V[u] > 0: G[v].append(V[u])\n",
    "        return max(uv + sum(sorted(vs, reverse=True)[:k]) for uv, vs in zip(V, G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        map = [[] for i in range(len(vals))]\n",
    "        for a, b in edges:\n",
    "            if vals[b] > 0:\n",
    "                map[a].append(vals[b])\n",
    "            if vals[a] > 0:\n",
    "                map[b].append(vals[a])\n",
    "        \n",
    "        ans = -inf\n",
    "        for v, l in zip(vals, map):\n",
    "            l.sort(reverse=True)\n",
    "            ans = max(ans, sum(l[:k]) + v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        map = [[] for i in range(n)]\n",
    "        for a, b in edges:\n",
    "            if vals[b] > 0:\n",
    "                map[a].append(vals[b])\n",
    "            if vals[a] > 0:\n",
    "                map[b].append(vals[a])\n",
    "        \n",
    "        ans = -inf\n",
    "        for v, l in zip(vals, map):\n",
    "            l.sort(reverse=True)\n",
    "            ans = max(ans, sum(l[:k]) + v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        s = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for a, b in edges:\n",
    "            if vals[a] > 0:\n",
    "                s[b].append(vals[a])\n",
    "            if vals[b] > 0:\n",
    "                s[a].append(vals[b])\n",
    "        ans = max(vals)\n",
    "        for i in range(n):\n",
    "            s[i].sort(reverse=True)\n",
    "            if len(s[i]) >= k:\n",
    "                ans= max(ans, vals[i] + sum(s[i][:k]))\n",
    "            else:\n",
    "                ans= max(ans, vals[i] + sum(s[i]))\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, w: List[int], e: List[List[int]], k: int) -> int:\n",
    "        n = len(w)\n",
    "        path = [[] for _ in range(n)]\n",
    "        for a, b in e:\n",
    "            path[b].append(w[a])\n",
    "            path[a].append(w[b])\n",
    "        \n",
    "        res = -inf\n",
    "        for i in range(0, n):\n",
    "            s1 = w[i]\n",
    "            if k:\n",
    "                for x in sorted(path[i], reverse = True)[:k]:\n",
    "                    if x <= 0:  break\n",
    "                    s1 += x\n",
    "            res = max(res, s1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, w: List[int], e: List[List[int]], k: int) -> int:\n",
    "        n = len(w)\n",
    "        path = [[] for _ in range(n)]\n",
    "        for a, b in e:\n",
    "            path[b].append(w[a])\n",
    "            path[a].append(w[b])\n",
    "        \n",
    "        res = -inf\n",
    "        for i in range(0, n):\n",
    "            s1 = w[i]\n",
    "            if k:\n",
    "                for x in sorted(path[i], reverse = True)[:k]:\n",
    "                    if x <= 0:  break\n",
    "                    s1 += x\n",
    "            res = max(res, s1)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        ans = -inf\n",
    "        for i in range(n):\n",
    "            cur = vals[i]\n",
    "            lst= [vals[j] for j in dct[i] if vals[j]>0]\n",
    "            lst.sort(reverse=True)\n",
    "            cur += sum(lst[:k])\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i, j in edges:\n",
    "            g[i].append(vals[j])\n",
    "            g[j].append(vals[i])\n",
    "        \n",
    "        for i in range(n):\n",
    "            g[i] = sorted(g[i], reverse=True)\n",
    "        \n",
    "        ans = float('-inf')\n",
    "        for i in range(n):\n",
    "            s = 0\n",
    "            for j in range(min(k, len(g[i]))):\n",
    "                if g[i][j] < 0: break\n",
    "                s += g[i][j]\n",
    "            ans = max(ans, vals[i] + s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        sl = [list() for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            sl[x].append(vals[y])\n",
    "            sl[y].append(vals[x])\n",
    "        ans = -inf\n",
    "        # print(sl)\n",
    "        for i in range(n):\n",
    "            # if len(sl[i]) >= k:\n",
    "            sl[i].sort(reverse=True)\n",
    "            cnt = 0\n",
    "            ni = len(sl[i])\n",
    "            for j in range(min(ni, k)):\n",
    "                if sl[i][j] > 0:\n",
    "                    cnt += sl[i][j]\n",
    "                else:\n",
    "                    break\n",
    "            ans = max(ans, cnt + vals[i])\n",
    "            # ans = max(ans, sum(sl[i][:k]) + vals[i])\n",
    "        return 0 if ans == -inf else ans\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            if vals[b] > 0:\n",
    "                g[a].append(vals[b])\n",
    "            if vals[a] > 0:\n",
    "                g[b].append(vals[a])\n",
    "        for bs in g.values():\n",
    "            bs.sort(reverse=True)\n",
    "        return max(v + sum(g[i][:k]) for i, v in enumerate(vals))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        return max(v + sum(nlargest(k, a)) for v, a in zip(vals, g))\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/maximum-star-sum-of-a-graph/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        return max(v + sum(nlargest(k, a)) for v, a in zip(vals, g))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x,y in edges:\n",
    "            if vals[y] > 0:\n",
    "                g[x].append(vals[y])\n",
    "            if vals[x] > 0:\n",
    "                g[y].append(vals[x])\n",
    "        return max(v+sum(nlargest(k,a)) for v,a in zip(vals,g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x,y in edges:\n",
    "            if vals[y] > 0:\n",
    "                g[x].append(vals[y])\n",
    "            if vals[x] > 0:\n",
    "                g[y].append(vals[x])\n",
    "        return max(v+sum(nlargest(k,a)) for v,a in zip(vals,g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x,y in edges:\n",
    "            if vals[x] > 0:\n",
    "                g[y].append(vals[x])\n",
    "            if vals[y] > 0:\n",
    "                g[x].append(vals[y])\n",
    "        return max(v+sum(nlargest(k,a)) for v,a in zip(vals,g))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        g = [[] for _ in range(len(vals))]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        for i, x in enumerate(g):\n",
    "            ans = max(ans, vals[i] + sum(nlargest(k, x)))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举+排序\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0:\n",
    "                g[x].append(vals[y])\n",
    "\n",
    "            if vals[x] > 0:\n",
    "                g[y].append(vals[x])\n",
    "\n",
    "        return max(v + sum(nlargest(k, a)) for v, a in zip(vals, g))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        return max(v + sum(nlargest(k, a)) for v, a in zip(vals, g))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 枚举+排序\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0:\n",
    "                g[x].append(vals[y])\n",
    "\n",
    "            if vals[x] > 0:\n",
    "                g[y].append(vals[x])\n",
    "\n",
    "        return max(v + sum(heapq.nlargest(k, a)) for v, a in zip(vals, g))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n=len(vals)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if vals[y]>0:\n",
    "                g[x].append(vals[y])\n",
    "            if vals[x]>0:\n",
    "                g[y].append(vals[x])\n",
    "        res=-sys.maxsize\n",
    "        for v, a in zip(vals, g):\n",
    "            res=max(res, v + sum(heapq.nlargest(k, a)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in vals]\n",
    "        for x, y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        return max(v + sum(nlargest(k, a)) for v, a in zip(vals, g))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        neighb = [[] for _ in vals]\n",
    "        for edge in edges:\n",
    "            if vals[edge[0]] > 0:\n",
    "                neighb[edge[1]].append(vals[edge[0]])\n",
    "            if vals[edge[1]] > 0:\n",
    "                neighb[edge[0]].append(vals[edge[1]])\n",
    "        ans = -inf\n",
    "        for v, nb in zip(vals, neighb):\n",
    "            ans = max(ans, v + sum(nlargest(k, nb)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        neighbour = collections.defaultdict(list)\n",
    "        \n",
    "        for a, b in edges :\n",
    "            neighbour[a].append(vals[b])\n",
    "            neighbour[b].append(vals[a])\n",
    "        to_ret = -1e99\n",
    "        for i in range(len(vals)) :\n",
    "            tempt = sorted(neighbour[i], reverse=True)[:k]\n",
    "            valt = vals[i] + sum([t for t in tempt if t > 0])\n",
    "            to_ret = max(to_ret, valt)\n",
    "        return to_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "\n",
    "        nb = defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            nb[a].append(vals[b])\n",
    "            nb[b].append(vals[a])\n",
    "\n",
    "        pnb = []\n",
    "        for i in range(n):\n",
    "            nb[i].sort(reverse=True)\n",
    "            # print(nb[i])\n",
    "            # tmp = \n",
    "            pnb.append(nb[i])\n",
    "\n",
    "        res = float('-inf')\n",
    "        for i in range(n):\n",
    "            tmp = vals[i]\n",
    "            j = 0\n",
    "            while j < k and j < len(pnb[i]):\n",
    "                if pnb[i][j] > 0:\n",
    "                    tmp += pnb[i][j]\n",
    "                j += 1\n",
    "            res = max(res, tmp)\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        nexts = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            nexts[a].append(b)\n",
    "            nexts[b].append(a)\n",
    "        res = float('-inf')\n",
    "        for node in range(n):\n",
    "            v = vals[node]\n",
    "            h = [-vals[nex] for nex in nexts[node]]\n",
    "            heapify(h)\n",
    "            for _ in range(k):\n",
    "                if not h: break\n",
    "                vn = heappop(h)\n",
    "                if vn >= 0: break\n",
    "                v -= vn\n",
    "            res = max(res, v)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return max(vals)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        ans = max(vals)\n",
    "        for u in range(len(vals)):\n",
    "            vs = [vals[v] for v in g[u] if vals[v] > 0]\n",
    "            s = vals[u] + sum(sorted(vs, reverse=True)[:min(len(vs), k)])\n",
    "            ans = max(ans, s)\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        for i in range(n):\n",
    "            g[i].sort(key=lambda i:-vals[i])\n",
    "        ret = -10 ** 9\n",
    "        for i in range(n):\n",
    "            s = vals[i]\n",
    "            # print(i, vals[i], g[i], [vals[x] for x in g[i]])\n",
    "            for j in range(min(k, len(g[i]))):\n",
    "                if vals[g[i][j]] <= 0:\n",
    "                    break\n",
    "                s += vals[g[i][j]]\n",
    "            ret = max(ret, s)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(vals[b])\n",
    "            graph[b].append(vals[a])\n",
    "        result = float('-inf')\n",
    "        for i in range(n):\n",
    "            tmp = sorted(graph[i],key=lambda x:-x)\n",
    "            left, right = 0, len(tmp)-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(tmp[mid] >= 0):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if(right < 0):\n",
    "                res = vals[i]\n",
    "            else:\n",
    "                res = vals[i] + sum(tmp[:min(k,right+1)])\n",
    "            result = max(result, res)\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(vals[b])\n",
    "            graph[b].append(vals[a])\n",
    "        result = float('-inf')\n",
    "        for i in range(n):\n",
    "            tmp = sorted(graph[i],key=lambda x:-x)\n",
    "            left, right = 0, len(tmp)-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(tmp[mid] >= 0):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            result = max(result, vals[i] + (sum(tmp[:min(k,right+1)]) if right >= 0 else 0))\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(vals[b])\n",
    "            graph[b].append(vals[a])\n",
    "        result = float('-inf')\n",
    "        for i in range(n):\n",
    "            tmp = sorted(graph[i],key=lambda x:-x)\n",
    "            left, right = 0, len(tmp)-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(tmp[mid] >= 0):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            res = vals[i] + (sum(tmp[:min(k,right+1)]) if right >= 0 else 0)\n",
    "            result = max(result, res)\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "      if k == 0:\n",
    "        return max(vals)\n",
    "\n",
    "      table = defaultdict(list)\n",
    "      for x, y in edges:\n",
    "        table[x].append(y)\n",
    "        table[y].append(x)\n",
    "\n",
    "      n = len(vals)\n",
    "      res = -float(\"inf\")\n",
    "      for i in range(n):\n",
    "        heap = []\n",
    "        for j in table[i]:\n",
    "          heappush(heap, vals[j])\n",
    "          if len(heap) > k:\n",
    "            heappop(heap)\n",
    "        # print(f\"i = {i}, vals[i] = {vals[i]}, heap = {heap}\")\n",
    "        res = max(res, sum(filter(lambda x: x > 0, heap)) + vals[i])\n",
    "\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        nodes_max_heap = {i: [] for i in range(len(vals))}\n",
    "        for edge in edges:\n",
    "            if edge[0] == edge[1]:\n",
    "                continue\n",
    "            if vals[edge[1]] >= 0:\n",
    "                heappush(nodes_max_heap[edge[0]], vals[edge[1]])\n",
    "                if len(nodes_max_heap[edge[0]]) > k:\n",
    "                    heappop(nodes_max_heap[edge[0]])\n",
    "\n",
    "            if vals[edge[0]] >= 0:\n",
    "                heappush(nodes_max_heap[edge[1]], vals[edge[0]])\n",
    "                if len(nodes_max_heap[edge[1]]) > k:\n",
    "                    heappop(nodes_max_heap[edge[1]])\n",
    "        \n",
    "            \n",
    "        # nodes_max_sums = [sum(list(values)) for values in nodes_max_heap.values()]\n",
    "        # nodes_max_sums = [nodes_max_sum +  for nodes_max_sum in nodes_max_sums]\n",
    "        max_sum = min(vals)\n",
    "        for i in range(len(vals)):\n",
    "            sums = sum(nodes_max_heap[i]) + vals[i]\n",
    "            if sums > max_sum:\n",
    "                max_sum = sums \n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import nlargest\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            if vals[y] > 0: g[x].append(vals[y])\n",
    "            if vals[x] > 0: g[y].append(vals[x])\n",
    "        \n",
    "        return max([v+sum(nlargest(k,a)) for v, a in zip(vals, g)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            start, end = edges[i]\n",
    "            # d[start].append([end, vals[end]])\n",
    "            # d[end].append([start, vals[start]])\n",
    "            d[start].append(vals[end])\n",
    "            d[end].append(vals[start])\n",
    "\n",
    "        import heapq\n",
    "        res = max(vals)\n",
    "        for key, v in d.items():\n",
    "            v.sort(key=lambda x: -x)\n",
    "            tmp_res = vals[key]\n",
    "            for i in range(min(k, len(v))):\n",
    "                if v[i] > 0:\n",
    "                    tmp_res += v[i]\n",
    "            res = max(res, tmp_res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxStarSum(self, vals, edges, m):\n",
    "        g = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            g[a].append(vals[b])\n",
    "            g[b].append(vals[a])\n",
    "        for k,item in g.items():\n",
    "            g[k] = sorted(g[k],key = lambda x:-x)\n",
    "        ans = max(vals)\n",
    "        for k in g.keys():\n",
    "            cur = vals[k]\n",
    "            item = g[k]\n",
    "            for i in range(min(len(item),m)):\n",
    "                if item[i] >= 0:\n",
    "                   cur += item[i]\n",
    "                else:\n",
    "                    break\n",
    "            ans = max(ans,cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        n = len(vals)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            graph[a].append([vals[b], b])\n",
    "            graph[b].append([vals[a], a])\n",
    "        for i in range(n):\n",
    "            graph[i] = sorted(graph[i], reverse=True)\n",
    "        def get_star_sum(array, k):\n",
    "            ans = 0\n",
    "            cnt = 0\n",
    "            for i in range(len(array)):\n",
    "                num = array[i][0]\n",
    "                if num > 0 and cnt < k:\n",
    "                    ans += num\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            return ans\n",
    "        \n",
    "        ans = float('-inf')\n",
    "        \n",
    "        seen = [0]*n\n",
    "        \n",
    "        for start in range(n):\n",
    "            if seen[start]:\n",
    "                continue\n",
    "            q = deque([start])\n",
    "            seen[start] = 1\n",
    "            while q:\n",
    "                node = q.popleft()\n",
    "                ans = max(ans, get_star_sum(graph[node], k)+vals[node])\n",
    "                for val, neighbor in graph[node]:\n",
    "                    if not seen[neighbor]:\n",
    "                        q.append(neighbor)\n",
    "                        seen[neighbor] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "\n",
    "    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return max(vals)\n",
    "        node2edge = defaultdict(set)\n",
    "        # for n in range(len(vals)):\n",
    "        #     node2edge[n].add(n)\n",
    "\n",
    "        for e1,e2 in edges:\n",
    "            node2edge[e1].add(e2)\n",
    "            node2edge[e2].add(e1)\n",
    "        max_result = -1e9\n",
    "        # 以每个节点为中心sort一下\n",
    "        for key in range(len(vals)):\n",
    "            ini_v = vals[key]# 初始值\n",
    "            ini_k = k\n",
    "            value = [vals[i] for i in node2edge[key]]\n",
    "            value.sort(reverse = True)\n",
    "            # print(ini_v, value)\n",
    "            # 注意一个问题： 最多k条边(k个额外节点)，可以是0条边\n",
    "            # 找到第一个小于0的idx，k=idx/k和idx取小\n",
    "            for idx in range(len(value)):\n",
    "                if value[idx]<=0:\n",
    "                    ini_k = min(ini_k, idx)\n",
    "                    break\n",
    "            # print(ini_k)\n",
    "            max_result = max(max_result, ini_v+sum(value[:ini_k]))\n",
    "        return max_result\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
